package com.xzz.backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: hhz
 * @create: 2022-01-10 15:56
 * 51. N 皇后
 * n皇后问题 研究的是如何将 n个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * <p>
 * 给你一个整数 n ，返回所有不同的n皇后问题 的解决方案。
 * <p>
 * 每一种解法包含一个不同的n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 **/
public class SolveNQueens {
    public static void main(String[] args) {
        System.out.println(solveNQueens(4));
        System.out.println(solveNQueens(8));
    }

    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        List<String> board = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(".");
        }
        for (int i = 0; i < n; i++) {
            board.add(sb.toString());
        }
        backtrack(board, 0, res);
        return res;
    }

    public static void backtrack(List<String> board, int row, List<List<String>> res) {
        if (row == board.size()) {
            res.add(new ArrayList<>(board));
            return;
        }
        int n = board.get(row).length();
        for (int col = 0; col < n; col++) {

            if (!isValid(board, row, col)) {
                continue;
            }

            String s = board.get(row);
            StringBuilder sb = new StringBuilder(s);
            sb.replace(col, col + 1, "Q");
            board.set(row, sb.toString());

            //回溯
            backtrack(board, row + 1, res);

            board.set(row, s);
        }

    }

    public static boolean isValid(List<String> board, int row, int col) {
        //因为排皇后是从上到下排的
        //所以 同一行 和 左下 右下的检测不需要
        int n = board.size();
        //检测同一列上有无已经存在的皇后
        for (int i = 0; i < n; i++) {
            String s = board.get(i);
            char c = s.charAt(col);
            if (c == 'Q') {
                return false;
            }
        }
        //检测 左上 有无已经存在的皇后
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            String s = board.get(i);
            char c = s.charAt(j);
            if (c == 'Q') {
                return false;
            }
        }
        //检测 右上 有无已经存在的皇后
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            String s = board.get(i);
            char c = s.charAt(j);
            if (c == 'Q') {
                return false;
            }
        }
        return true;
    }
}
